package com.hzdp.sort;

/**
 * 分治思路,选定一个数据,将比他大的放右边,比他小的放左边。递归
 * 
 * 最坏情况O(n^2),最好情况/平均情况O(nlogn)
 * 
 * @author liuming
 * 
 */
public class QuickSort {

	public static void swap(int[] array, int i1, int i2) {
		int temp = array[i1];
		array[i1] = array[i2];
		array[i2] = temp;
	}

	public static void quickSort(int[] array, int s, int e) {
		if (s >= e) {
			return;
		}
		int i = s;
		int j = e;

		while (i < j) {
			while (j > i && array[j] >= array[i])
				j--;
			if (i < j) {
				swap(array, j, i);
				i++;
			}
			while (j > i && array[j] >= array[i])
				i++;
			if (i < j) {
				swap(array, j, i);
				j--;
			}
		}
		quickSort(array, s, i - 1);
		quickSort(array, i + 1, e);
	}

	public static void main(String[] args) {
		int[] array = { 2, 32, 10, 0, 2, 11, 30, 2, 4, 5, 1, 2 };
		quickSort(array, 0, array.length - 1);
		for (int i : array) {
			System.out.print(i + ",");
		}
	}
}
